1. Field of the Invention
This invention relates to systems and methods for transforming an arbitrary graph into a spanning tree, such as a rooted and directed spanning tree, with means for providing guidance regarding preservation and pruning of paths in the graph.
2. Background of the Invention
Many data sets are structured as directed graphs, wherein nodes can be linked to any other node without regard to a hierarchical structure. For example, Internet websites or any corpus of hyperlinked documents can include links to and from one another without regard to any hierarchical structure.
Algorithms exist for converting directed graphs to spanning trees, such as a rooted and directed spanning tree. For example, a taxonomy may often be in the form of a rooted and directed spanning tree. In particular, these algorithms seek to find a maximum or minimum number of optimum branchings. Examples of such an algorithm include the Edmonds algorithm and the Chu-Liu/Edmunds algorithm. These algorithms take into account the structure of the graph, but they cannot take advantage of relationships and preferences that require human judgment or insight.
Of course, one could manually transform a directed graph into a spanning tree, such as a rooted and directed spanning tree, by tediously inspecting each node and deciding which paths to preserve and which to omit. However, this process may be impossible for large graphs.